package LeetCodeSection;/*
 *
 *@author:    Xavier
 *@data:      2023 - 08 - 20
 *@time:      14:29
 *
 */


import java.util.Stack;

//8. 二叉树的最近公共祖先
//https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
public class TheMostRecentCommonAncestor {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }


 class Solution {
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        Stack<TreeNode> s1 = new Stack<>();
        getPath(root, p, s1);

        Stack<TreeNode> s2 = new Stack<>();
        getPath(root, p , s2);

        int size1 = s1.size();
        int size2 = s2.size();

        if (size1 > size2) {
            int size = size1 - size2;
            while (size != 0) {
                s1.pop();
                size--;
            }
        }else {
            int size = size2 - size1;
            while (size != 0) {
                s2.pop();
                size--;
            }
        }

        // 此时两栈中的元素个数相等
        while(!s1.empty() && !s2.empty()) {
            TreeNode tmp1 = s1.pop();
            TreeNode tmp2 = s2.pop();
            if (tmp1 == tmp2) {
                return tmp1;
            }
        }
        return null;
    }

    public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack){
        if (root == null) {
            return false;
        }
        stack.push(root);
        if (root == node) {
            return true;
        }
        boolean ret = getPath(root.left, node, stack);
        if (ret == true) {
            return true;
        }
        boolean ret2 = getPath(root.right, node, stack);
        if (ret2 == true) {
            return true;
        }
        stack.pop();
        return false;
    }

//-------------------------------------------------------------------------------------------
        //方法一

        public  TreeNode lowestCommonAncestor (TreeNode root, TreeNode p, TreeNode q){
            if (root == null) {
                return null;
            }
            //p q 其中有一个为root
            if (p == root || q == root) {
                return root;
            }

            TreeNode leftRet = lowestCommonAncestor(root.left, p, q);
            TreeNode rightRet = lowestCommonAncestor(root.right, p, q);
            //p q 分别在root左右两边
            if (leftRet != null && rightRet != null) {
                return root;
                //此时右边为空 那么共同祖先在left
            } else if (leftRet != null) {
                return leftRet;
            } else {
                return rightRet;
            }

        }
    }




}

